import random

#得到子欧拉圈
def subEulercircuit(E,v0):
    circuit=tuple([v0])
    S=set({})
    while (circuit[0]!= circuit[-1] or len(circuit)==1):
        y=circuit[-1]
        for (u,v) in E:
            if(u==y):
                circuit=circuit+tuple([v])
                E=E-{(u,v)}
                S=S|{(u,v)}
                break
    return [circuit,S]
            
def set2V(E):
    V=set({})
    for (u,v)in E:
        V=V |{u,v}
    return V

#构建一个从v0出发的欧拉圈
def Eulercircuit(E,v0):
    [circuit,S]= subEulercircuit(E,v0)
    E=E-S
    while(E != set({})):
        V1=set( circuit)
        V2=set2V(E)
        V1V2=V1&V2 
        for v0 in V1V2:
            [subcircuit,S] =subEulercircuit(E,v0)
            if S==set({}):
                continue
            k=circuit.index(v0)
            circuit= circuit[0:k] +subcircuit+circuit[ k+1:-1] +tuple([circuit[-1]])
            E=E-S
            break 
    return circuit

#构建一个复杂的节点度为偶数复杂图
def replacevertex(V0,E0,n):
    V=set(V0)
    E=set({})
    for k in range(n):
        [u0,v0]=random.sample(list(V),2)
        V=V-{u0}
        E=set({})
        for (u,v) in E0:
            if u==u0:
                E=E|{(v0,v)}
            elif v==u0:
                E=E|{(u,v0)}
            else:
                E=E|{(u,v)}
        E0=E 
    return [V,E]

#求G=<V,E>的邻接表Ea
def adjacentlist(V,E):
    Ea=[]
    for w in V:
        e0=[w]
        e1=[]
        for (u,v) in E:
            if u == w and (v not in e1):
                e1=e1+[v]
            if v==w and(u not in e1):
                e1=e1+[u]
        e0=e0+[sorted(e1)]
        Ea=Ea+[e0]
    return sorted(Ea)

#哈密顿图节点周游问题
def tourpath0(V,E,path,m):
    while(len(path)<m):
        w=path[-1]
        i=V.index(w)
        E1=E[i]
        E2=E1[1]
        for u in E2:
            if(u not in path):
                path.append(u)
                break
        if(path[-1]==w):
            break
    return path

def tourpath1(V,E,path,m):
    v=path.pop()
    while(len(path)!=0):
        u=path[-1]
        i=V.index(u)
        E1=E[i]
        E2=E1[1]
        k=E2.index(v)
        while(k<(len(E2)-1)):
            k=k+1
            v=E2[k]
            if(v not in path):
                path.append(v)
                break
        if(u != path[-1]):
            break
        v=path.pop()
    return path
           
def tourpath(V,E,path,m):
    if(len(path)== m):
        path=tourpath1(V,E,path,m)
    while(len(path)!= 0):
        path=tourpath0(V,E,path,m)
        if(len(path)==m):
            break
        path =tourpath1(V,E,path,m)
    return path
    
def Hamiltonpath(V,E,v0):
    global Ea, paths
    V=sorted(V)
    Ea=adjacentlist(V,E)
    paths=set({})
    path=[v0]
    m=len(V)
    path=tourpath(V,Ea,path,m)
    paths=paths|{tuple(path)}
    k=1
    while(len(path)==m):
        path =tourpath(V,Ea,path,m)
        if len(path)==m:
            paths=paths |{tuple(path)}
            k=k+1
    return paths

#骑士周游图
def Knighttouregraph(n):
    P8=[[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]
    N=n*n
    V=list(range(N))
    E=set({})
    for k in range(N):
        j=k%n 
        i=int(k/n)
        for [u,v] in P8:
            if 0<=(i+u)and (i+u)<n and 0<=(j+v) and (j+v)<n:
                E=E|{(k,(i+u)*n+(j+v))}
    return [V,E]

#求加权图的顶点度
def degreesetw(V,E):
    V=sorted(V)
    m=len(V)
    di=[0]*m 
    do=[0]*m 
    d=[0]*m
    for (w,u,v) in E:
        i=V.index(u)
        j=V.index(v)
        di[j]+=1
        do[i]+=1 
        d[i]+=1 
        d[j]+=1 
    return [d,di,do]
                                 
#最短路径
def shortpath(V,E,di,Hx,path,zn):
    Pm=[]
    for p in path:
        vn=p[-1]
        if vn==zn:
            Pm=Pm +[p]
            continue
        if di[V.index(vn)] != 0:
            Pm=Pm +[p]
            continue
        for (w,u,v) in E:
            if u==vn:
                kv=V.index(v)
                if di[kv]>0:
                    di[kv]=di[kv]-1 
                vw=p[0]+w
                if vw<=Hx[kv]:
                    Hx[kv]=vw
                    e=[vw] +p[1:]+[v]
                    Pm=Pm +[e]
    return [di,Hx,Pm]

def shortestpath(V,E,v0,vn):
    V=sorted(V)
    [d,di,do]=degreesetw(V,E)
    Pm0=[]
    Pm=[[0,v0]]
    inf= 10000
    Hx= [inf for x in range(len(V))]
    Hx[0]=0
    while Pm0!=Pm:
        Pm0=Pm
        [di,Hx,Pm]=shortpath(V,E,di,Hx,Pm0,vn)
    Pm=sorted(Pm)
    return [Hx,Pm]

#关键路径
def stepu0v(di0,E):
    S=set({})
    for u0 in di0:
        for (w,u,v) in E:
            if u == u0:
                S=S|{(w,u,v)}
    return S
        
def stepuv0(do0,E):
    S=set({})
    for v0 in do0:
        for (w,u,v) in E:
            if v == v0:
                S=S|{(w,u,v)}
    return S

def TEpath(S,Hx,di):
    di0=set({})
    for (w,u,v) in S:
        if Hx[v]<Hx[u]+w:
            Hx[v]=Hx[u]+w 
        if di[v]>0:
            di[v]=di[v]-1 
        if di[v] == 0:
            di0=di0|{v}
    return [Hx,di,di0]

def TLpath(S,Hy,do):
    do0=set({})
    for (w,u,v) in S:
        if Hy[u]> Hy[v]-w:
            Hy[u]=Hy[v]-w 
        if do[u]>0:
            do[u]=do[u]-1 
        if do[u] == 0:
            do0=do0|{u}
    return [Hy,do,do0]

#求最早完成时间
def craticalTE(V,E,di,v0,vn):
    Hx=[0]*len(V)

    di0={v0}
    while vn not in di0:
        S=stepu0v(di0,E)
        [Hx,di,di0]=TEpath(S,Hx,di)
        E=E-S
    return Hx

#最迟完成时间
def craticalTL(V,E,do,Hn,v0,vn):
    Hy=[1000]* len(V)
    Hy[len(V)-1]=Hn
    do0={vn}
    while v0 not in do0:
        S=stepuv0(do0,E)
        [Hy,do,do0]=TLpath(S,Hy,do)
        E=E-S
    return Hy

#求关键路径
def craticalpath(V,E,di,do,v0,vn):
    Hx=craticalTE( V,E,di,v0,vn)
    Hn=Hx[len(V)-1]
    Hy=craticalTL(V,E,do,Hn,v0,vn)
    V=list(V)
    N=len(V)
    C=set({})
    for k in range(N):
        if Hx[k] == Hy[k]:
            C=C|{V[k]}
    Pc=set({})
    for (w,u,v) in E:
        if u in C and v in C:
            Pc=Pc |{(w,u,v)}
    return [Pc,Hx,Hy]

#判断给定的图是否是二分图
def isbigraph(V,E,V1,V2):
    tv=(V==V1|V2)
    tv=tv&(V1&V2==set({}))
    for (u,v) in E:
        tv=tv&(u in V1)&(v in V2)
    return tv

#生成(m,n)完全二分图
def completebigraph(m,n):
    V0=set({})
    V1=set({})
    for k in range(m):
        V0=V0|{'x'+str(k)}
    for k in range(n):
        V1=V1|{'y'+str(k)}
        E=set({})
    for u in V0:
        for v in V1:
            E=E|{(u,v)}
    return [V0,V1,E]

#从一个(n,m)二分图，随机抽取N条边构成一个二分图
def createbigrath(m,n,N):
    [V0,V1,E0]=completebigraph(m,n)
    E=random.sample(list(E0),N)
    return [V0,V1,E]

#对于一个二分图，求匹配以及匹配的边集合
def baiscmatch(V,E):
    match=[]
    Em=set({})
    for (u,v) in E:
        if u not in match and v not in match:
            match=match+[u]+[v]
            Em=Em|{(u,v)}
    return [match,Em]

#匈牙利算法
#求路径上饱和节点集合
def saturatedV(path):
    Vs=set(path)
    return Vs

#求不饱和节点集合
def unsaturatedV(V,Vs):
    Vu=V-Vs
    return Vu

#基于路径求匹配集合
def path2match(V1,V2,path):
    match=set({})
    n=len(path)
    for k in range(0,n,2):
        u=path[k]
        v=path[k+1]
        if u in V1:
            match=match|{(u,v)}
        else:
            match = match|{(v,u)}
    return match

#基于路径path求一次增广路径
def augmentpath(Vu,Eu,path):
    v0=path[0]
    un=path[-1]
    u0=-1
    vn=-1
    for(u,v)in Eu:
        if(v==v0)and(u in Vu):
            u0=u
        if(u==v0) and (v in Vu):
            u0=v
    for(u,v)in Eu:
        if(v== un) and (u in Vu):
            vn=u
        if(u==un)and(v in Vu):
            vn=v
    if(u0!=-1) and(vn!=-1):
        path=[u0]+path+[vn]
    return path

#基于路径path求最长增广路径
def augmentpaths(V,E,path):
    Vs=saturatedV(path)
    Vu=unsaturatedV(V,Vs)
    Eu=E
    m=0
    while len(path)!=m:
        m=len(path)
        path=augmentpath(Vu,Eu,path)
        Vs=saturatedV(path)
        Vu = unsaturatedV(V,Vs)
    return path

#求最大匹配集
def matchmaxset( V1,V2,E,path):
    Vu=V1|V2
    Eu=E
    match=set({})
    matchset=set({})
    Vs=set({})
    m=0
    while len(path)!= m:
        m=len(path)
        path= augmentpaths(Vu,Eu,path)
        match = path2match(V1,V2,path)
        matchset=matchset|match
        Vs=Vs|saturatedV(path)
        Eu=E
        for(u,v)in E:
            if(u in Vs)or (v in Vs):
                Eu=Eu-{(u,v)}
        if Eu==set({}):
            break
        for (u,v) in Eu:
            break
        match=set({})
        path=[u,v]
        m=0
    return matchset